Public key cryptography uses an asymmetric algorithm in which the encryption and decryption keys are different and for which it is infeasible to compute one key knowing only the other. Users receive (or, with suitable hardware or software, can generate for themselves) a pair of keys—that is, two large numbers. The user keeps one of these keys private and never discloses it. The other key can be safely made public, just like a phone number or similar personal data. Because of the nature of the algorithm and the way the keys are generated, information encrypted with the private key can only be decrypted with the public key and vice versa. So the sender and receiver do not need to share any secret.
Public key cryptography enables several possibilities:
Anyone knowing the user's public key can send the user a message encrypted with that key and can be sure that only the user—who alone has the private key—can decrypt it. This provides confidentiality.
The user might also encrypt a message with his private key. This cannot provide confidentiality, because anyone who knows the public key can decrypt it. But the fact that they can decrypt it means the message must have come from the user—who alone has the private key. This provides integrity and authentication and can also be used as a basis for non-repudiation—the digital equivalent of a signature.
If a sender signs a message with her own private key and then encrypts authentication and non-repudiation are provided together.
In practice, things are actually more complex. In the first example, for performance and operational reasons, the sender will choose a random symmetric session key and use a symmetric cipher to encrypt the message. The public key will be used to encrypt just the session key. Similarly, in the second example, the user will first “digest” the message he wishes to sign, and encrypt the digest with his private key; the recipient will recompute the digest and compare its value with the value he decrypts from the user. A digest is a mathematical construct with a relatively short fixed length, which is derived from an arbitrarily long message; it has the essential property that it is infeasible, knowing a message and a corresponding digest, to compute another message with the same digest.
All the processing is done by software; the real human users do not really “do” any of this.
It is important to understand that public keys do not actually have to be published to the world. They can be shared as widely or narrowly as business and privacy requirements dictate.
In prior art public keys can be linked together to form a public key infrastructure—a PKI. The links are data structures (or data files) called certificates. Here is how it works:
Alice may decide to register her public key (and identity information) with a Registration Authority (RA). (In this description of prior art, the usual names “Alice” and “Bob” are used to describe the roles of signatory and relying party, respectively.)
Using the information collected by the RA, a Certificate Authority (CA) may then create a computer file containing Alice's public key together with information which identifies Alice and a validity period. The CA signs the file with its own private key, creating a certificate.
A CA's public key may in its turn be certified by another CA; and that CA's certificate will be certified by another and so on until eventually there is a root, that is, an unsigned (or self-signed) public key whose value has to be known some other way.
So starting from a root it is possible to traverse a certificate chain to discover a public key value.
A set of public keys linked in this way form a public key infrastructure. The simplest PKI has a single CA which acts as the root and which signs all the certificates. It is also possible to build a PKI in prior art using cross-certification instead of a hierarchy, but the end result is broadly the same.
Anybody with the right software can be an RA or a CA; whatever the legal or business constraints, there is no technical requirement for an authority to be authorised by anybody.
It is important to understand that the linking of a public key into a PKI does not affect what can be done with the matching private key. Some common misconceptions can be clarified as follows:
A certificate is “used” by a relying party, not by a holder of a private key. The relying party extracts from the certificate the public key to be used for encryption or signature checking.
A certificate is not needed to create a digital signature or to decrypt a received message.
A user does not need to be named in any certificate at all to check someone else's signature or to send them an encrypted message.
Not even an Advanced Electronic Signature (as defined in the EU Electronic Signatures Directive) requires a certificate to exist in respect of the matching public key.
A typical method in which a PKI is implemented in prior art is as follows.
As well as agreeing to look after her private key, Alice applies her ordinary handwritten signature to a paper application form which references “certificate policies” and “certificate practice statements”.
Alice then constructs and signs a PKCS#10 object which she sends to her RA. PKCS#10 is an industry standard data format.
The RA checks the contents of the received object against what it knows about Alice and sends a certificate request to a CA.
The CA signs, and sends to Alice, a certificate upon which any Bob in the world can rely. The certificate will probably have an expiry date a year or so in the future. Alice might have to remember to take action to renew the certificate when it expires, perhaps again using a handwritten signature for that purpose.
When Alice digitally signs anything, her software sends the certificate to the relying party along with her signature block and the object that has been signed.
When Bob receives the transmission, he (that is, his software) first examines the certificate, and checks that it is within its period of validity. If he recognises the “issuer”, and knows the issuer's public key, he can also check the signature on the certificate. If it computes, he can extract the public key from the certificate and check the signature on the data that was signed.
Except, of course, that he might not know the public key of the issuer. He now needs a chain of certificates which link to a public key that he does know. Perhaps Alice sent him the chain, or perhaps he has to search public directories to assemble it himself. He may or may not have to pay a charge to access a directory. Bob needs to process the chain by checking that the issuer name in one certificate is the same as the subject name in the next, that all the signatures on all the certificates check out, and that the validity periods within the chain make sense relative to each other. There is a possibility, of course, that no chain can be constructed which includes both the original certificate and a certificate signed by any public key he knows implicitly.
Except, of course, that the original certificate, or any of the certificates in the chain, may have been revoked. So Bob's software must now go in turn to an Internet address (URL—Uniform Resource Locator) included in each certificate, extract the most recent certificate revocation list (CRL) from that URL, and check that the serial number of the next certificate in the chain does not appear. He may or may not have to pay a charge for access to each CRL.
As an alternative to the last three bullets, Bob can instead pass the certificate to a validation authority (VA) which will do much of the work for him, and return to him a signed go/no-go response on the validity of the original certificate. If validation services are sufficiently integrated, they may be able to succeed more often than Bob alone could. Use of a validation service will probably be chargeable.
Bob archives the certificate of interest and either the rest of the chain and the CRLs or the signed validation response. To guard against later revocation of Alice's certificate, Bob would also do well to get from a timestamp authority a timestamp of the signature block on the signed data to prove that he had it in his possession before the revocation occurred.
Ever since the invention of public key cryptography, the vision has been held out of a universal infrastructure that would enable everyone in the world to verify with assurance the digital signatures of everyone else. Electronic transactions exploiting this infrastructure would acquire the important properties of integrity and non-repudiation.
Achievement of the vision would empower individuals because they could digitally sign anything, anywhere, any time. And it would consequently deliver business competitiveness—a typical company, already participating in one e-marketplace as a buyer perhaps, could smoothly enter another, perhaps as a seller, with the same identity. This vision has the potential to alter the nature—and the economics—of the e-marketplace concept. The whole world could develop rapidly into a single e-marketplace—an integrated e-economy.
The prior art does not easily enable subjects to participate in a public key infrastructure with an ability to sign anything, anywhere. Key-pairs in the prior art are generally seen as part of a “managed identity” rather than an extension of personality, independent of certification.
The prior art PKI is largely relevant only in a managed identity context in which a subject is related directly with a single affiliate and the identity only makes sense within that context. For example, an affiliation as an employee, as a customer of a bank, or as a vendor to a major corporation etc. Having acquired or generated a key-pair, the subject convinces a single business partner (a bank, for example, or an employer, or a major customer) of the binding of the subject's identity to its public key. Any particular individual would be likely to have multiple managed identities outstanding at any one time.
A further major problem with the prior art in delivering the universal infrastructure vision is that the CA's contract is typically with the subject and not with the relying party. There is a realisation among traditional CA businesses that the subject will be unwilling to pay the full cost—or perhaps any part of the cost—of “being issued with a certificate”.
There is a furthermore a perverse liability issue which arises from the fact that the CA's contract is with Alice—the subject named in the certificate—and not with Bob—who relies on its correctness. In prior art PKI any per-certificate liability is unbounded, because whoever signed the certificate never gets to know who is relying on it until there is a problem. Alice can send the same certificate to a million Bobs and the CA will never know how much liability is building up. The “value” of a certificate can be reused and reused without the CA (the source of that value) ever becoming aware.
Directive 1999/93/EC of the European Parliament and of the Council of 13 Dec. 1999 on a Community framework for electronic signatures (“the Directive”) defines a number of the terms used in the present document. However, the definition of “certificate” is wider in the present document than in the Directive; the Directive's use of this word corresponds to the use in the present document of the term “verification certificate”. The term “digital signature” in the present document is a technique for implementing the Directive's notion of an “advanced electronic signature”.